package com.yuan.linklist;

import lombok.ToString;

import java.util.HashMap;
import java.util.Stack;
import java.util.concurrent.BrokenBarrierException;

/**
 * @ClassName: singlelinklist
 * @Description: TODO
 * @Author MrYuan
 * @Date: 2021/3/16 9:50
 * @Version 1.0
 */
public class singlelinklist {
    public static void main(String[] args) {
        Node w = new Node(1, "w");
        Node l = new Node(2, "l");
        SingleLinkList singleLinkList = new SingleLinkList();
        singleLinkList.add(w);
        singleLinkList.add(l);
//        singleLinkList.list();
        Node g = new Node(3, "g");
        singleLinkList.addByOrder(g);
//        singleLinkList.list();
        //length
//        System.out.println(getLength(singleLinkList.head));
//返回链表倒数第几个元素
//        Node lastByIndex = findLastByIndex(singleLinkList.head, 0);
//        System.out.println(lastByIndex);
        //反转链表
//        reverseList(singleLinkList.head);
//        singleLinkList.list();
        //栈输出
//        outlist(singleLinkList.head);
        //合并两个有序个链表
        //fanzhuan
        singleLinkList.list();
        singleLinkList.head = ReverseList(singleLinkList.head);
        singleLinkList.list();
    }

    public static class SingleLinkList {
        private Node head = new Node(0, "");

        private void add(Node node) {
            Node temp = head;
            while (true) {
                if (temp.next == null) {
                    break;
                }
                temp = temp.next;
            }
            temp.next = node;
        }

        private void addByOrder(Node node) {
            Node temp = head;
            boolean flg = false;
            while (true) {
                if (temp.next == null) {
                    break;
                }
                if (temp.next.no > node.no) {
                    break;
                }
                if (temp.next.no == node.no) {
                    flg = true;
                    break;
                }
                temp = temp.next;
            }
            if (flg) {
                System.out.println("idcunz");
            } else {
                node.next = temp.next;
                temp.next = node;
            }
        }

        private void list() {
            Node temp = head;
            while (true) {
                if (temp == null) {
                    break;
                }
                System.out.println(temp);
                temp = temp.next;
            }
        }
    }

    public static class Node {
        private int no;
        private String nodeName;
        private Node next;

        public Node(int no, String nodeName) {
            this.no = no;
            this.nodeName = nodeName;
        }

        @Override
        public String toString() {
            return "no " + no + ",nodename " + nodeName;
        }
    }

    //面试题，1，获取节点个数,不带头节点
    private static int getLength(Node node) {
        int length = 0;
        Node temp = node.next;
        while (true) {
            if (temp == null) {
                break;
            }
            temp = temp.next;
            ++length;
        }
        return length;
    }

    //查找1链表的倒数第几个节点
    public static Node findLastByIndex(
            Node head, int index
    ) {
        if (head.next == null) {
            return null;
        }
        int length = getLength(head);
        if (index < 0 || index > length) {
            return null;
        }
        Node curr = head;
        for (int i = 0; i < length - index; i++) {
            curr = curr.next;
        }
        return curr;
    }

    //反转链表
    public static void reverseList(Node head) {
        if (head.next == null || head.next.next == null) {
            return;
        }
        Node cur = head.next;
        Node next = null;
        Node reverseHead = new Node(0, "");
        while (cur != null) {
            next = cur.next;
            cur.next = reverseHead.next;
            reverseHead.next = cur;
            cur = next;
        }
        head.next = reverseHead.next;
    }

    //倒序输出链表，用栈结构实现
    private static void outlist(Node head) {
        System.out.println("kaishi");
        if (head == null) {
            return;
        }
        Stack<Node> nodes = new Stack<Node>();
        Node cur = head.next;
        while (cur != null) {
            nodes.push(cur);
            cur = cur.next;
        }
        while (nodes.size() > 0) {
            System.out.println(nodes.pop());
        }
    }


    public static Node ReverseList(Node head) {
        if (head == null) {
            return null;
        }
        Node pre = null;
        Node next = null;
        while (head != null) {
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

